1. Field of the Invention
The present invention relates to a process for protecting a computer system implementing a cryptographic algorithm that uses a secret key. More precisely, the purpose of the process is to produce a version of the algorithm that is not vulnerable to a certain type of physical attackxe2x80x94known as Differential Power Analysis or High-Order Differential Power Analysisxe2x80x94aimed at obtaining information on the secret key through a study of the computer system""s electric power consumption during the execution of the calculation.
The cryptographic algorithms considered herein use a secret key to calculate output information as a function of input information; this can involve an operation for encryption, decryption, signature, signature verification, authentication or non-repudiation. They are constructed in such a way that in practice, an attacker who knows the inputs and the outputs cannot deduce any information on the secret key itself.
The invention described herein relates to a class larger than that traditionally designated by the expression xe2x80x9csecret key algorithmsxe2x80x9d or xe2x80x9csymmetric algorithms.xe2x80x9d In particular, everything that is described in the present patent application also applies to so-called xe2x80x9cpublic keyxe2x80x9d algorithms or xe2x80x9casymmetric algorithms,xe2x80x9d which actually include two keys: one public, the other private and undisclosed, the latter being the one targeted by the attacks described below.
2. Description of Related Art
Attacks of the type known as Power Analysis, developed by Paul Kocher and Cryptographic Research (see the document Introduction to Differential Power Analysis and Related Attacks by Paul Kocher, Joshua Jaffe, and Benjamin Jun, Cryptography Research, 870 Market Street, Suite 1008, San Francisco, Calif. 94102; published as an HTML document at the URL address: http://www.cryptography.com/dpa/technical/index.html, introduced into the present application as a reference) is based on the observation that, in reality, an attacker can acquire information other than just the input and output data during the execution of the calculation such as, for example, the electric power consumption of the microcontroller or the electromagnetic radiation emitted by the circuit.
Differential Power Analysis, abbreviated DPA, is an attack that makes it possible to obtain information on the secret key contained in the computer system by performing a statistical analysis on power consumption measurements performed on a large number of calculations with this same key.
As a non-limiting example, the case of the DES (Data Encryption Standard) algorithm, a description of which can be found in any of the following named documents will be considered:
FIPS PUB 46-2, Data Encryption Standard, 1994;
FIPS PUB 74, Guidelines for Implementing and Using the NBS Data Encryption Standard, 1981;
ANSI X3.92 American National Standard, Data Encryption Algorithm, 1981;
ISO/IEC 8731:1987, Bankingxe2x80x94Approved Algorithms for Message Authenticationxe2x80x94Part 1: Data Encryption Algorithm (DEA);
or in the following book:
Bruce Schneier, Applied Cryptography, 2nd Edition, John Wiley and Sons, 1996, page 270.
The above-mentioned documents are introduced into the present application as references.
The DES algorithm is executed in 16 steps known as rounds (see FIG. 1a). In each of the 16 rounds, a transformation F into 32 bits is performed. This transformation F uses eight nonlinear transformations of 6 bits to four bits, each of which is coded into a table called an S box (see FIG. 1b, in which the S boxes are marked S1, S2, . . . , S8.
A DPA attack on the DES can be implemented in the following way:
1st step: Power consumption measurements are made on the first round, for 1,000 DES calculations. The input values of these 1,000 calculations are marked E[1], . . . , E[1,000]. The corresponding 1,000 power consumption curves measured during these calculations are marked C[1], . . . , C[1,000]. The average curve CM of the 1,000 consumption curves is also calculated.
2nd step: The first bit output from the first S box during the first round is selected. Let b be the value of this bit. It is easy to see that b is only dependent on 6 bits of the secret key. The attacker forms a hypothesis on the 6 bits in question. He calculatesxe2x80x94from these 6 bits and from the E[i]sxe2x80x94the corresponding theoretical values for b. This makes it possible to separate the 1,000 inputs E[1], . . . , E[1,000] into two categories: those that result in b=0, and those that result in b=1.
3rd step: Next, the average CMxe2x80x2 of the curves corresponding to inputs of the first category, i.e., those for which b=0, is calculated. If CM and CMxe2x80x2 show a notable difference, the values retained for the 6 key bits are considered to be the correct ones. If CM and CMxe2x80x2 do not show any substantial difference in the statistical sense, i.e., no difference that is clearly greater than the typical difference from the noise measured, the 2nd step is repeated with another choice for the 6 bits.
4th step: Steps 2 and 3 are repeated with a target bit b output from the second S box, then from the third S box, and so on, through the eighth S box. Thus, 48 bits of the secret key are eventually obtained.
5th step: The remaining 8 bits can be found by a thorough search.
This attack does not require any knowledge of the individual power consumption of each instruction, or of the chronological position of each of these instructions. It applies in the same way whenever it may be assumed that the attacker knows some of the outputs of the algorithm and the corresponding consumption curves. It is based only on the fundamental hypothesis according to which:
Fundamental Hypothesis
There is an intermediate variable, appearing during the calculation of the algorithm, such that the knowledge of some key bits, in practice less than 32 bits, makes it possible to determine whether two inputs, and respectively two outputs, do or do not result in the same value for this variable.
All of the algorithms, like the DES, that use S boxes are potentially vulnerable to DPA, since the normal modes of implementation generally fall within the scope of the above-mentioned hypothesis.
The attacks known as High-Order Differential Power Analysis, abbreviated HO-DPA, are a generalization of the DPA attack described above. They can use several different sources of information; in addition to power consumption, they can involve measurements of electromagnetic radiation, temperature, etc., and can use statistical operations that are more sophisticated than the simple concept of an average, and intermediate variables (generalizing the bit b defined above) that are less elementary. Nonetheless, they are based on exactly the same fundamental hypothesis as DPA.
The object of the process that is the subject of the present invention is to eliminate the risks of DPA or HO-DPA attacks on computer systems using secret or private key cryptography.
Consequently, another subject of the present invention is a modification of the cryptographic calculation process implemented by protected computer systems using cryptography such that the above-mentioned fundamental hypothesis is no longer verified, in other words, no intermediate variable is dependent on the power consumption of an easily accessible subsystem of the private or secret key, attacks of the DPA or HO-DPA type thus being rendered inoperative.
The process for protecting a computer system implementing a standard cryptographic calculation process that uses a secret key, which is the subject of the present invention, is remarkable in that the cryptographic calculation process is separated into several distinct calculation parts, executed in parallel and producing partial intermediate results distinct from those of the standard cryptographic calculation, and in that the final value obtained by the standard calculation without a separation is reconstructed from the distinct partial intermediate results. The term standard cryptographic calculation process is intended to mean any sequential or successive calculation process that makes it possible to obtain encrypted values, decrypted values, and signature, signature verification, authentication, and non-repudiation values. A process of this type makes it possible to prevent DPA or HO-DPA type attacks against embedded systems equipped with cryptographic calculation functions, such as smart cards dedicated to credit card, ATM card, access control card or similar functions.